#include <iostream>

using namespace std;

struct TreeNode{
    int key;
    TreeNode *left,*right;
    TreeNode(){
        left=NULL;
        right=NULL;
    }
};

class Tree{
private:
    TreeNode *tree;

public:
    
    void InorderTree(TreeNode *node)
    {
        if(node!=NULL)
        {
            InorderTree(node->left);
            cout<<node->key<<" ";
            InorderTree(node->right);
        }
    }
    
    TreeNode* SearchTree(int k)
    {
        TreeNode *node=tree;
        while(node!=NULL&&node->key!=k)
        {
            if(k<node->key)
                node=node->left;
            else
                node=node->right;
        }
        return node;
    }
    
    TreeNode *GetTreeTop()
    {
        return tree;
    }
    
    void InsertTree(int k)
    {
        TreeNode *newnode=new TreeNode;
        newnode->key=k;
        TreeNode *tmp,*node=tree;
        while(node!=NULL&&node->key!=k)
        {
            tmp=node;
            if(k<node->key)
                node=node->left;
            else
                node=node->right;
        }
        if(node!=NULL&&node->key==k)
            cout<<k<<": The key has already exsit!"<<endl;
        if(tmp==NULL)
            tree=newnode;
        else
        {
            if(tmp->key>k)
                tmp->left=newnode;
            else
                tmp->right=newnode;
        }
    }
    
    void DeleteTree(int k)
    {
        if(tree==NULL)
            cout<<"The tree is empty"<<endl;
        TreeNode *tmp,*node=tree;
        while(node!=NULL&&node->key!=k)
        {
            tmp=node;
            if(k<node->key)
                node=node->left;
            else
                node=node->right;
        }
        if(node==NULL)
            cout<<"The node doesn't exsit"<<endl;
        else
        {
            if(node->left==NULL && node->right==NULL)
            {
                if(tmp->key>k)
                    tmp->left=NULL;
                else
                    tmp->right=NULL;
            }
            else if(node->left==NULL || node->right==NULL)
            {
                node=(node->left==NULL)?node->right:node->left;
                if(tmp->key>node->key)
                    tmp->left=node;
                else
                    tmp->right=node;
            }
            else{
                
            }
        }
    }
};